package 回溯;

import java.util.LinkedHashSet;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 拆分字符串使唯一子字符串的数目最大1593.java
 * @createTime 2023年03月09日 11:49:00
 */
public class 拆分字符串使唯一子字符串的数目最大1593 {
	public static void main(String[] args) {
		System.out.println(maxUniqueSplit("ababccc"));
	}
	static LinkedHashSet<String> existStr = new LinkedHashSet<>();

	static int max = 0;

	public static int maxUniqueSplit(String s) {
		char[] chars = s.toCharArray();
		backTrace(chars, chars.length, 0);
		return max;
	}

	public static void backTrace(char[] chars, int length, int curIndex) {
		//结束条件，到了最后
		if (curIndex == length) {
			max = Math.max(max, existStr.size());
			return;
		}
		//循环遍历字符串
		StringBuilder sb = new StringBuilder();
		for (int i = curIndex; i < length; i++) {
			sb.append(chars[i]);
			//校验这个字符是否已经存在了,则继续
			if (existStr.contains(sb.toString())) {
				continue;
			}
			existStr.add(sb.toString());
			backTrace(chars, length, i + 1);
			existStr.remove(sb.toString());
		}
	}
}
